Spatial database systems are configured to store and manage spatial data. One particular type of spatial database system is a geographical information system (GIS). A GIS is configured to store and operate on geospatial data, or data relating to features on the Earth's surface. Within-distance queries are frequently used in spatial database systems. Given a first spatial object, a within-distance query searches for other spatial objects within a certain distance of the first spatial object. One example of a within-distance query is a query for all cities within a distance of a highway.
The performance of within-distance queries is an important aspect of these systems because of the computational complexity of spatial data searching. Spatial objects can be complex in nature. For example, spatial objects may be represented by geometries defined by many vertices and/or edges. Computing distances between a query geometry and candidate geometries based on their edges and vertices is an expensive operation with respect to time. Often, within-distance queries are used to benchmark the performance of a spatial database system.
Typically, an R-tree index is built ahead of time on candidate geometries, thereby avoiding full table scans when searching for within-distance candidates. Nodes in the R-tree index each correspond to a minimum bounding region, such as a minimum bounding rectangle (MBR). The R-tree index creation process generates a MBR for each indexed spatial object. Ancestor nodes in the R-tree index correspond to MBRs that contain the MBR of every descendant node of the ancestor node.
One method to optimize within-distance queries is to eliminate spatial objects as potential matches within a specified distance. Distances are calculated between an approximation of the first spatial object and approximations of the other spatial objects. The MBR is often used as the approximation. It is much faster to compute distances between the MBRs, which can help eliminate spatial objects that are not within the specified distance. More expensive computations are only necessary if the approximation calculations are not conclusive. However, an MBR often does not accurately describe the first object, and very little advantage is gained.
Thus, there is a need for a solution that effectively speeds up within-distance queries.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.